The introduction of programmable logic devices (PLD) was a true revolution in the hardware design world. It enabled engineers to shrink circuits requiring several devices onto a single device thus simplifying their designs while saving space and power. Traditionally, PLDs have been used in combinational circuits such as address decoders as well as sequential circuits such as bus arbitration schemes. During the last few years, advances and improvements in PLD architectures enabled the devices to grow more complex while addressing the never-ending quest for higher density and faster speeds. Despite these improvements, engineers still face certain problems and limitations when implementing state machine designs with PLDs.
A typical programmable logic device is composed of a user-programmable AND array, a fixed or programmable OR gates or arrays, followed by macrocells comprising output registers, feedback paths to the programmable AND array, and output pads. The existence of a feedback path from the output registers to the AND array makes PLDs ideal candidates for state machine implementations.
There are several basic categories of state machines such as Mealy and Moore machines. FIG. 1 illustrates the basics of a Mealy state machine as follows: a logic circuit 10, inputs 12 from the outside world, current state inputs 14, outputs 16, and next state outputs 18 leading to flip-flops 20.
The main characteristic of the Mealy is that its outputs 16, to the outside world, are a function of both inputs 12 and inputs 14.
It is possible to implement any of the state machines in a PLD; however, there are inefficiencies in implementing state machines with current PLDs.
If a Mealy machine is implemented on a standard PLD, a wasteful two macrocells would be required -- one per state register and one for each output.
The use of an extra macrocell is not an efficient use of the device's realestate resources and is fairly limiting in application. For example, a state machine with four outputs would be constrained to having no more than four state variables in an eight macrocell PLD.
FIG. 2 illustrates that if a Mealy machine is implemented on a standard PLD, a wasteful two macrocells would be required. In operation, inputs 28, lead to both logic circuit 30 and 40, comprising an AND and OR matrix. Logic circuit 30 generates the next state then outputs to register 32, working as memory elements. The output of register 32 is the current state, which is then input to logic circuits 30 and 40. Logic circuit 40 has the current state and inputs 28 as inputs for decoding and then outputting over pads 44. The current state is also used to generate the next state when inputted to circuit 30.
Inefficiencies occur in that pads 34 are by-passed and not used and that flip-flops 42 are likewise by-passed and not used. Specifically, both macrocell 33 and 43 are under-utilized.
As a solution to the aforementioned state machine problem, a two-OR array circuit was designed. One array generates the next state and utilizes the register. A second array calculates the outputs utilizing the current state and the inputs. FIG. 3 is a block diagram of a two OR array PLD utilized for implementing a Mealy state machine, and having the following elements: input 50, programmable logical AND array 52, a first programmable logical OR array 54, macrocell 55 having flip-flop 56 and output pad 62, feedback line 58, and a second logical OR array 60.
One skilled in the art will appreciate the advantage of this architecture. Specifically, by implementing two OR arrays, which have a common output pad, the first OR will calculate the current state of the Mealy machine, and the second OR will calculate the outputs in response to the current state and the inputs. Thus, implementing a Mealy state machine by utilizing only one flip-flop and one output pad per state register of the machine.
Therefore, a need exists for a macrocell which can coordinate the outputs from two logical OR arrays for implementing an efficient Mealy state machine, and specifically, the efficient use of output pads and registers/flip-flops.